<!DOCTYPE html>












  


<html class="theme-next pisces use-motion" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
























<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2">

<link rel="stylesheet" href="/css/main.css?v=7.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.1.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/logo1.jpg?v=7.1.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/logo1.jpg?v=7.1.0">


  <link rel="mask-icon" href="/images/logo.svg?v=7.1.0" color="#222">







<script id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '7.1.0',
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
    back2top: true,
    back2top_sidebar: false,
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="Golang有很多新语法特性，在实现算法的时候相对于C++很简单很多，相对也更容易理解。说实话看了一段时间的golang倒不觉得有什么，但是当需要自己写的时候，还是会觉得有点点别扭和不习惯。">
<meta name="keywords" content="算法">
<meta property="og:type" content="article">
<meta property="og:title" content="Algorithm Implemented In Golang">
<meta property="og:url" content="https://luoo.oschina.io/2017/09/29/tech/Algorithm Implemented In Golang/index.html">
<meta property="og:site_name" content="从你的全世界路过">
<meta property="og:description" content="Golang有很多新语法特性，在实现算法的时候相对于C++很简单很多，相对也更容易理解。说实话看了一段时间的golang倒不觉得有什么，但是当需要自己写的时候，还是会觉得有点点别扭和不习惯。">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-04-14T12:28:00.700Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Algorithm Implemented In Golang">
<meta name="twitter:description" content="Golang有很多新语法特性，在实现算法的时候相对于C++很简单很多，相对也更容易理解。说实话看了一段时间的golang倒不觉得有什么，但是当需要自己写的时候，还是会觉得有点点别扭和不习惯。">



  <link rel="alternate" href="/atom.xml" title="从你的全世界路过" type="application/atom+xml">



  
  
  <link rel="canonical" href="https://luoo.oschina.io/2017/09/29/tech/Algorithm Implemented In Golang/">



<script id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>Algorithm Implemented In Golang | 从你的全世界路过</title>
  












  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">从你的全世界路过</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <p class="site-subtitle">心智渐开，世事渐杂</p>
      
    
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">

    
    
    
      
    

    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">

    
    
    
      
    

    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">

    
    
    
      
    

    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">

    
    
    
      
    

    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-schedule">

    
    
    
      
    

    

    <a href="/schedule/" rel="section"><i class="menu-item-icon fa fa-fw fa-calendar"></i> <br>计划</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-you">

    
    
    
      
    

    

    <a href="/you/" rel="section"><i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br>知遇</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-about">

    
    
    
      
    

    

    <a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>

  </li>

      
      
    </ul>
  

  

  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://luoo.oschina.io/2017/09/29/tech/Algorithm Implemented In Golang/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="方林">
      <meta itemprop="description" content="愿你出走半生，归来仍是少年">
      <meta itemprop="image" content="/images/logo1.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="从你的全世界路过">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">Algorithm Implemented In Golang

              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2017-09-29 22:20:25" itemprop="dateCreated datePublished" datetime="2017-09-29T22:20:25+08:00">2017-09-29</time>
            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/编程技术/" itemprop="url" rel="index"><span itemprop="name">编程技术</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2017/09/29/tech/Algorithm Implemented In Golang/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2017/09/29/tech/Algorithm Implemented In Golang/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>Golang有很多新语法特性，在实现算法的时候相对于C++很简单很多，相对也更容易理解。<br>说实话看了一段时间的<code>golang</code>倒不觉得有什么，但是当需要自己写的时候，还是会觉得有点点别扭和不习惯。</p>
<a id="more"></a>
<p>先构建我们的抽象基类<br><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">type</span> Sortable <span class="keyword">interface</span> &#123;</span><br><span class="line">	Len() <span class="keyword">int</span></span><br><span class="line">	Less(<span class="keyword">int</span>, <span class="keyword">int</span>) <span class="keyword">bool</span></span><br><span class="line">	Swap(<span class="keyword">int</span>, <span class="keyword">int</span>)</span><br><span class="line">	Slice(<span class="keyword">int</span>, <span class="keyword">int</span>) Sortable</span><br><span class="line">	Get(<span class="keyword">int</span>) <span class="keyword">interface</span>&#123;&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">type</span> IntArr []<span class="keyword">int</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(array IntArr)</span> <span class="title">Len</span><span class="params">()</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">len</span>(array)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(array IntArr)</span> <span class="title">Less</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	<span class="keyword">return</span> array[i] &lt; array[j]</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(array IntArr)</span> <span class="title">Swap</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	array[i], array[j] = array[j], array[i]</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(array IntArr)</span> <span class="title">Slice</span><span class="params">(i <span class="keyword">int</span>, j <span class="keyword">int</span>)</span> <span class="title">Sortable</span></span>  &#123;</span><br><span class="line">	<span class="keyword">return</span> array[i:j]</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="params">(array IntArr)</span> <span class="title">Get</span><span class="params">(i <span class="keyword">int</span>)</span> <span class="title">interface</span></span>&#123;&#125;  &#123;</span><br><span class="line">	<span class="keyword">return</span> array[i]</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<hr>
<h3 id="快排及演变"><a href="#快排及演变" class="headerlink" title="快排及演变"></a>快排及演变</h3><p>快排是一种比较常见的排序方法，它的Partition思想也用在很多地方。<code>golang</code>中的<code>slice</code>是一种引用类型，不需要在参数上传入类似C++的指针，同时<code>slice</code>的切割相当方便简单，相对于C++看起来要简单一些</p>
<figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">QuickSort</span><span class="params">(arr Sortable)</span></span>  &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> || arr.Len() == <span class="number">1</span> &#123;</span><br><span class="line">		<span class="keyword">return</span></span><br><span class="line">	&#125;</span><br><span class="line">	arrLen := arr.Len()</span><br><span class="line">	pivot := rand.Intn(arrLen - <span class="number">1</span>)</span><br><span class="line">	head, tail := <span class="number">0</span>, arrLen - <span class="number">1</span></span><br><span class="line">	<span class="keyword">for</span> head &lt;= tail &#123;</span><br><span class="line">		<span class="keyword">if</span> !arr.Less(head, pivot) &#123;</span><br><span class="line">			arr.Swap(head, pivot)</span><br><span class="line">			pivot = head</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> arr.Less(tail, pivot) &#123;</span><br><span class="line">			arr.Swap(tail, pivot)</span><br><span class="line">			pivot = tail</span><br><span class="line">		&#125;</span><br><span class="line">		head++</span><br><span class="line">		tail--</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> pivot &gt; <span class="number">1</span> &#123;</span><br><span class="line">		QuickSort(arr.Slice(<span class="number">0</span>, pivot<span class="number">-1</span>))</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> pivot &lt; arrLen - <span class="number">2</span> &#123;</span><br><span class="line">		QuickSort(arr.Slice(pivot+<span class="number">1</span>, arrLen))</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>基于Partition思想的变形题，如何查找旋转数组（有序数组截断头部一段拼接到尾部）的最小值</p>
<figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">FindRotateMin</span><span class="params">(arr Sortable)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	arrLen := arr.Len()</span><br><span class="line">	<span class="keyword">if</span> arrLen == <span class="number">1</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">	&#125;</span><br><span class="line">	min, max := <span class="number">0</span>, arrLen - <span class="number">1</span></span><br><span class="line">	<span class="keyword">for</span> min + <span class="number">1</span> &lt; max &#123;</span><br><span class="line">		mid := (min + max)/<span class="number">2</span></span><br><span class="line">		<span class="keyword">if</span> arr.Less(mid, min) &#123;</span><br><span class="line">			max = mid</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> arr.Less(max, mid) &#123;</span><br><span class="line">			min = mid</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> arr.Get(max).(<span class="keyword">int</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="打印1到最大的n位数"><a href="#打印1到最大的n位数" class="headerlink" title="打印1到最大的n位数"></a>打印1到最大的n位数</h3><p>输入： n [int]<br>输出： 1~最大的n位数</p>
<figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">PrintMaxn</span><span class="params">(n <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> n &lt; <span class="number">1</span> &#123;</span><br><span class="line">		<span class="built_in">panic</span>(<span class="string">"ILLEGAL ARGS"</span>)</span><br><span class="line">	&#125;</span><br><span class="line">	buf := <span class="built_in">make</span>([]<span class="keyword">byte</span>, n)</span><br><span class="line">	<span class="keyword">for</span> k := <span class="keyword">range</span> buf &#123;</span><br><span class="line">		buf[k] = <span class="string">'0'</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> &#123;</span><br><span class="line">		buf[n<span class="number">-1</span>]++</span><br><span class="line">		max := <span class="literal">false</span></span><br><span class="line">		<span class="keyword">for</span> i := n<span class="number">-1</span>; i &gt; <span class="number">0</span>; i-- &#123;</span><br><span class="line">			<span class="keyword">if</span> buf[i] == <span class="string">'9'</span> + <span class="number">1</span> &#123;</span><br><span class="line">				buf[i] = <span class="string">'0'</span></span><br><span class="line">				buf[i<span class="number">-1</span>] += <span class="number">1</span></span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> buf[<span class="number">0</span>] == <span class="string">'9'</span> + <span class="number">1</span> &#123;</span><br><span class="line">				max = <span class="literal">true</span></span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> max &#123;</span><br><span class="line">			<span class="keyword">break</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">println</span>(strings.TrimLeft(<span class="keyword">string</span>(buf), <span class="string">"0"</span>))</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="顺时针打印矩阵"><a href="#顺时针打印矩阵" class="headerlink" title="顺时针打印矩阵"></a>顺时针打印矩阵</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Clockwise</span><span class="params">(arr [][]<span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">	height := <span class="built_in">len</span>(arr)</span><br><span class="line">	width := <span class="built_in">len</span>(arr[<span class="number">0</span>])</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> height == <span class="number">1</span> &#123;</span><br><span class="line">		<span class="keyword">if</span> width == <span class="number">1</span> &#123;</span><br><span class="line">			fmt.Print(arr[<span class="number">0</span>][<span class="number">0</span>], <span class="string">"\t"</span>)</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">for</span> i:=<span class="number">0</span>; i&lt; width; i++ &#123;</span><br><span class="line">				fmt.Print(arr[<span class="number">0</span>][i], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="keyword">if</span> width == <span class="number">1</span> &#123;</span><br><span class="line">			<span class="keyword">for</span> i:=<span class="number">0</span>; i&lt; height; i++ &#123;</span><br><span class="line">				fmt.Print(arr[i][<span class="number">0</span>], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">for</span> i:=<span class="number">0</span>; i&lt; width; i++ &#123;</span><br><span class="line">				fmt.Print(arr[<span class="number">0</span>][i], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">for</span> i:=<span class="number">1</span>; i&lt; height; i++ &#123;</span><br><span class="line">				fmt.Print(arr[i][width<span class="number">-1</span>], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">for</span> i:=width<span class="number">-2</span>; i&gt;=<span class="number">0</span>; i-- &#123;</span><br><span class="line">				fmt.Print(arr[height<span class="number">-1</span>][i], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">for</span> i:=height<span class="number">-2</span>; i&gt;<span class="number">0</span>; i-- &#123;</span><br><span class="line">				fmt.Print(arr[i][<span class="number">0</span>], <span class="string">"\t"</span>)</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">if</span> height - <span class="number">2</span> &gt; <span class="number">0</span> &amp;&amp; width - <span class="number">2</span> &gt; <span class="number">0</span> &#123;</span><br><span class="line">		arrNew := arr[<span class="number">1</span>:height<span class="number">-1</span>]</span><br><span class="line">		<span class="keyword">for</span> key, value := <span class="keyword">range</span> arrNew &#123;</span><br><span class="line">			arrNew[key] = value[<span class="number">1</span>:width<span class="number">-1</span>]</span><br><span class="line">		&#125;</span><br><span class="line">		Clockwise(arrNew)</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="出栈顺序校验"><a href="#出栈顺序校验" class="headerlink" title="出栈顺序校验"></a>出栈顺序校验</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">StackPopOrder</span><span class="params">(input []<span class="keyword">int</span>, pop []<span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> input == <span class="literal">nil</span> || pop == <span class="literal">nil</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> <span class="built_in">len</span>(input) != <span class="built_in">len</span>(pop) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">	&#125;</span><br><span class="line">	length := <span class="built_in">len</span>(input)</span><br><span class="line">	stack := list.List&#123;&#125;</span><br><span class="line">	c := <span class="number">0</span></span><br><span class="line">	i := <span class="number">0</span></span><br><span class="line">	<span class="keyword">for</span> i = <span class="number">0</span>; i &lt; length; &#123;</span><br><span class="line">		<span class="keyword">if</span> stack.Len() == <span class="number">0</span> || stack.Back().Value.(<span class="keyword">int</span>) != pop[i] &#123;</span><br><span class="line">			<span class="keyword">if</span> c &lt; length &#123;</span><br><span class="line">				stack.PushBack(input[c])</span><br><span class="line">				c++</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">			&#125;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			stack.Remove(stack.Back())</span><br><span class="line">			i++</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> c == length &amp;&amp; i == length &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="二叉搜索树的后续遍历校验"><a href="#二叉搜索树的后续遍历校验" class="headerlink" title="二叉搜索树的后续遍历校验"></a>二叉搜索树的后续遍历校验</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">SearchTreePostOrder</span><span class="params">(arr []<span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">	&#125;</span><br><span class="line">	length := <span class="built_in">len</span>(arr)</span><br><span class="line">	<span class="keyword">if</span> length &lt; <span class="number">2</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">	&#125;</span><br><span class="line">	pivot := arr[length<span class="number">-1</span>]</span><br><span class="line">	i := <span class="number">0</span></span><br><span class="line">	<span class="keyword">for</span> i = <span class="number">0</span>; i &lt; length; &#123;</span><br><span class="line">		<span class="keyword">if</span> arr[i] &lt; pivot &#123;</span><br><span class="line">			i++</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">break</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> j := i; j &lt; length; j++ &#123;</span><br><span class="line">		<span class="keyword">if</span> arr[j] &lt; pivot &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> SearchTreePostOrder(arr[<span class="number">0</span>:i]) &amp;&amp; SearchTreePostOrder(arr[i+<span class="number">1</span>:])</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="全排序"><a href="#全排序" class="headerlink" title="全排序"></a>全排序</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Permutation</span><span class="params">(arr []<span class="keyword">byte</span>, index <span class="keyword">int</span>)</span></span>  &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> || index &lt; <span class="number">0</span> &#123;</span><br><span class="line">		<span class="keyword">return</span></span><br><span class="line">	&#125;</span><br><span class="line">	length := <span class="built_in">len</span>(arr)</span><br><span class="line">	<span class="keyword">if</span> length == index + <span class="number">1</span> &#123;</span><br><span class="line">		<span class="built_in">println</span>(<span class="keyword">string</span>(arr))</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> i := index; i &lt; length; i++ &#123;</span><br><span class="line">		arr[i], arr[index] = arr[index], arr[i]</span><br><span class="line">		Permutation(arr, index + <span class="number">1</span>)</span><br><span class="line">		arr[i], arr[index] = arr[index], arr[i]</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="全组合"><a href="#全组合" class="headerlink" title="全组合"></a>全组合</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Combination</span><span class="params">(arr []<span class="keyword">byte</span>)</span> [] <span class="title">string</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">nil</span></span><br><span class="line">	&#125;</span><br><span class="line">	current := []<span class="keyword">string</span>&#123;<span class="keyword">string</span>(arr[<span class="number">0</span>])&#125;</span><br><span class="line">	<span class="keyword">if</span> <span class="built_in">len</span>(arr) == <span class="number">1</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> current</span><br><span class="line">	&#125;</span><br><span class="line">	sub := Combination(arr[<span class="number">1</span>:])</span><br><span class="line">	<span class="keyword">for</span> _, v := <span class="keyword">range</span> sub &#123;</span><br><span class="line">		current = <span class="built_in">append</span>(current, v + <span class="keyword">string</span>(arr[<span class="number">0</span>]))</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">append</span>(current, sub...)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="最大连续子数组和"><a href="#最大连续子数组和" class="headerlink" title="最大连续子数组和"></a>最大连续子数组和</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">MaxSubArraySum</span><span class="params">(arr []<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> &#123;</span><br><span class="line">		<span class="built_in">panic</span>(<span class="string">"无效参数"</span>)</span><br><span class="line">	&#125;</span><br><span class="line">	length := <span class="built_in">len</span>(arr)</span><br><span class="line">	subSum := <span class="built_in">make</span>([]<span class="keyword">int</span>, length)</span><br><span class="line">	result := arr[<span class="number">0</span>]</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> k1, v1 := <span class="keyword">range</span> arr &#123;</span><br><span class="line">		tmp := <span class="built_in">make</span>([]<span class="keyword">int</span>, length - k1)</span><br><span class="line">		tmp[<span class="number">0</span>] = v1</span><br><span class="line">		<span class="keyword">for</span> k2, v2 := <span class="keyword">range</span> arr[k1+<span class="number">1</span>:] &#123;</span><br><span class="line">			tmp[k2 + <span class="number">1</span>] = tmp[k2] + v2</span><br><span class="line">		&#125;</span><br><span class="line">		subSum[k1] = tmp[<span class="number">0</span>]</span><br><span class="line">		<span class="keyword">for</span> _, v3 := <span class="keyword">range</span> tmp &#123;</span><br><span class="line">			<span class="keyword">if</span> v3 &gt; subSum[k1] &#123;</span><br><span class="line">				subSum[k1] = v3</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> _, v4 := <span class="keyword">range</span> subSum &#123;</span><br><span class="line">		<span class="keyword">if</span> v4 &gt; result &#123;</span><br><span class="line">			result = v4</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="1的个数"><a href="#1的个数" class="headerlink" title="1的个数"></a>1的个数</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">OneCount</span><span class="params">(x <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> x &lt; <span class="number">0</span> &#123;</span><br><span class="line">		<span class="built_in">panic</span>(<span class="string">"参数错误"</span>)</span><br><span class="line">	&#125;</span><br><span class="line">	data := <span class="built_in">make</span>([]<span class="keyword">int</span> , x+<span class="number">1</span>)</span><br><span class="line">	data[<span class="number">0</span>] = <span class="number">0</span></span><br><span class="line">	data[<span class="number">1</span>] = <span class="number">1</span></span><br><span class="line">	<span class="keyword">if</span> x &lt; <span class="number">2</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> data[x]</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> i := <span class="number">2</span>; i &lt;= x; i++ &#123;</span><br><span class="line">		count := <span class="number">0</span></span><br><span class="line">		t := i</span><br><span class="line">		<span class="keyword">for</span> t &gt; <span class="number">0</span> &#123;</span><br><span class="line">			<span class="keyword">if</span> t%<span class="number">10</span> == <span class="number">1</span> &#123;</span><br><span class="line">				count++</span><br><span class="line">			&#125;</span><br><span class="line">			t = t/<span class="number">10</span></span><br><span class="line">		&#125;</span><br><span class="line">		data[i] = data[i<span class="number">-1</span>] + count</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> data[x]</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="数组的最小数字排序"><a href="#数组的最小数字排序" class="headerlink" title="数组的最小数字排序"></a>数组的最小数字排序</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">ArrayToMaxNumber</span><span class="params">(arr []<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	sort.Slice(arr, Compare)</span><br><span class="line">	str := <span class="string">""</span></span><br><span class="line">	<span class="keyword">for</span> _, v := <span class="keyword">range</span> arr &#123;</span><br><span class="line">		str += strconv.Itoa(v)</span><br><span class="line">	&#125;</span><br><span class="line">	number, _ := strconv.Atoi(str)</span><br><span class="line">	<span class="keyword">return</span> number</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Compare</span><span class="params">(x_ <span class="keyword">int</span>, y_ <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">	x := strconv.Itoa(x_)</span><br><span class="line">	y := strconv.Itoa(y_)</span><br><span class="line">	xlen, ylen:= <span class="built_in">len</span>(x), <span class="built_in">len</span>(y)</span><br><span class="line">	length := xlen</span><br><span class="line">	<span class="keyword">if</span> ylen &lt; xlen &#123;</span><br><span class="line">		length = ylen</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> i := <span class="number">0</span>; i &lt; length; i++ &#123;</span><br><span class="line">		<span class="keyword">if</span> x[i] == y [i] &#123;</span><br><span class="line">			<span class="keyword">continue</span></span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span> x[i] &lt; y[i] &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> xlen == ylen &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> length == ylen &#123;</span><br><span class="line">		xn, _ := strconv.Atoi(x[length:])</span><br><span class="line">		<span class="keyword">return</span> Compare(xn, y_)</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		yn, _ := strconv.Atoi(y[length:])</span><br><span class="line">		<span class="keyword">return</span> Compare(x_, yn)</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="求第x个丑数"><a href="#求第x个丑数" class="headerlink" title="求第x个丑数"></a>求第x个丑数</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">GetnthUglyNumber</span><span class="params">(n <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	ugly := <span class="built_in">make</span>([]<span class="keyword">int</span>, n)</span><br><span class="line">	ugly[<span class="number">0</span>] = <span class="number">1</span></span><br><span class="line">	index2 := <span class="number">0</span></span><br><span class="line">	index3 := <span class="number">0</span></span><br><span class="line">	index5 := <span class="number">0</span></span><br><span class="line">	<span class="keyword">for</span> i := <span class="number">1</span>; i &lt; n ; i++ &#123;</span><br><span class="line">		number := min(ugly[i<span class="number">-1</span>]*<span class="number">2</span>, ugly[i<span class="number">-1</span>]*<span class="number">3</span>, ugly[i<span class="number">-1</span>]*<span class="number">5</span>)</span><br><span class="line">		<span class="keyword">if</span> number == ugly[i<span class="number">-1</span>]*<span class="number">2</span> &#123;</span><br><span class="line">			index2++</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> number == ugly[i<span class="number">-1</span>]*<span class="number">3</span> &#123;</span><br><span class="line">			index3++</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> number == ugly[i<span class="number">-1</span>]*<span class="number">5</span> &#123;</span><br><span class="line">			index5++</span><br><span class="line">		&#125;</span><br><span class="line">		ugly[i] = number</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ugly[n<span class="number">-1</span>]</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">min</span><span class="params">(a <span class="keyword">int</span>, b <span class="keyword">int</span>, c <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	minNum := a</span><br><span class="line">	<span class="keyword">if</span> b &lt; minNum &#123;</span><br><span class="line">		minNum = b</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> c &lt; minNum &#123;</span><br><span class="line">		minNum = c</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> minNum</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="数组中的逆序对数量"><a href="#数组中的逆序对数量" class="headerlink" title="数组中的逆序对数量"></a>数组中的逆序对数量</h3><figure class="highlight golang"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">ReversePairCount</span><span class="params">(arr []<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> arr == <span class="literal">nil</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">	&#125;</span><br><span class="line">	length := <span class="built_in">len</span>(arr)</span><br><span class="line">	<span class="keyword">if</span> length == <span class="number">1</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">	&#125;</span><br><span class="line">	mid := length/<span class="number">2</span></span><br><span class="line">	left := arr[<span class="number">0</span>:mid]</span><br><span class="line">	right := arr[mid:]</span><br><span class="line">	count := <span class="number">0</span></span><br><span class="line">	<span class="keyword">for</span> i,j := mid - <span class="number">1</span>, length - mid <span class="number">-1</span>; i &gt;= <span class="number">0</span> &amp;&amp; j &gt;= <span class="number">0</span>; &#123;</span><br><span class="line">		<span class="keyword">if</span> left[i] &gt; right[j] &#123;</span><br><span class="line">			count++</span><br><span class="line">			j--</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			i--</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> count + ReversePairCount(left) + ReversePairCount(right)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>

    

    
    
    

    

    
      
    
    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/09/09/tech/GolangChannel/" rel="next" title="GolangChannel">
                <i class="fa fa-chevron-left"></i> GolangChannel
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/03/06/tech/SQL语句Tips/" rel="prev" title="SQL语句Tips">
                SQL语句Tips <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  
    <div class="comments" id="comments">
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/logo1.jpg" alt="方林">
            
              <p class="site-author-name" itemprop="name">方林</p>
              <div class="site-description motion-element" itemprop="description">愿你出走半生，归来仍是少年</div>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">27</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  
                    
                      <a href="/categories/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">3</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  
                    
                      <a href="/tags/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">17</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="https://github.com/yourname" title="GitHub &rarr; https://github.com/yourname" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="mailto:sean_ps@163.com" title="E-Mail &rarr; mailto:sean_ps@163.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            </div>
          

          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-block">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                Links
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://www.luoo.net" title="http://www.luoo.net" rel="noopener" target="_blank">落网</a>
                  </li>
                
              </ul>
            </div>
          

          
            
          
          

        </div>
      </div>

      
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#快排及演变"><span class="nav-number">1.</span> <span class="nav-text">快排及演变</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#打印1到最大的n位数"><span class="nav-number">2.</span> <span class="nav-text">打印1到最大的n位数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#顺时针打印矩阵"><span class="nav-number">3.</span> <span class="nav-text">顺时针打印矩阵</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#出栈顺序校验"><span class="nav-number">4.</span> <span class="nav-text">出栈顺序校验</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二叉搜索树的后续遍历校验"><span class="nav-number">5.</span> <span class="nav-text">二叉搜索树的后续遍历校验</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#全排序"><span class="nav-number">6.</span> <span class="nav-text">全排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#全组合"><span class="nav-number">7.</span> <span class="nav-text">全组合</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最大连续子数组和"><span class="nav-number">8.</span> <span class="nav-text">最大连续子数组和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1的个数"><span class="nav-number">9.</span> <span class="nav-text">1的个数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组的最小数字排序"><span class="nav-number">10.</span> <span class="nav-text">数组的最小数字排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#求第x个丑数"><span class="nav-number">11.</span> <span class="nav-text">求第x个丑数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组中的逆序对数量"><span class="nav-number">12.</span> <span class="nav-text">数组中的逆序对数量</span></a></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      

      

    </div>
  </aside>
  


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">fanglin</span>

  

  
</div>









        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

    

    
  </div>

  

<script>
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  <script src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>


  


  <script src="/js/utils.js?v=7.1.0"></script>

  <script src="/js/motion.js?v=7.1.0"></script>



  
  


  <script src="/js/affix.js?v=7.1.0"></script>

  <script src="/js/schemes/pisces.js?v=7.1.0"></script>



  
  <script src="/js/scrollspy.js?v=7.1.0"></script>
<script src="/js/post-details.js?v=7.1.0"></script>



  


  <script src="/js/next-boot.js?v=7.1.0"></script>


  

  

  

  
  

<script src="//cdn1.lncld.net/static/js/3.11.1/av-min.js"></script>



<script src="//unpkg.com/valine/dist/Valine.min.js"></script>

<script>
  var GUEST = ['nick', 'mail', 'link'];
  var guest = 'nick,mail,link';
  guest = guest.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#comments',
    verify: true,
    notify: false,
    appId: 'jjdDCzDO6jlN5yOgAbnVwdJ3-gzGzoHsz',
    appKey: 'jnjP7aorboCG7pJV6HvdMP15',
    placeholder: 'ヾﾉ≧∀≦)o来啊，快活啊!',
    avatar: 'mm',
    meta: guest,
    pageSize: '10' || 10,
    visitor: false,
    lang: 'zh-cn' || 'zh-cn'
  });
</script>




  


  




  

  

  

  

  

  

  

  

  

  

  

  

  

  

</body>
</html>
